import java.util.LinkedList;
import java.util.Queue;

public class J101102 {
    public static class BinaryTree {

        static class TreeNode {
            public char val;
            public TreeNode left;//左孩子的引用
            public TreeNode right;//右孩子的引用
            public TreeNode(){
            }
            public TreeNode(char val) {
                this.val = val;
                left = null;
                right = null;
            }
        }


        /**
         * 创建一棵二叉树 返回这棵树的根节点
         *
         * @return
         */
        TreeNode root = new TreeNode('0');

        public BinaryTree(){
           root.left = new TreeNode('1');
           root.right = new TreeNode('2');
           root.left.left = new TreeNode('3');
           root.left.right = new TreeNode('4');
           root.right.left = new TreeNode('5');
           root.right.right = new TreeNode('6');
        }

        // 前序遍历
        public void preOrder(TreeNode root) {
            if(root == null){
                return;
            }
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }

        // 中序遍历
        void inOrder(TreeNode root) {
            if(root == null){
                return;
            }
            preOrder(root.left);
            System.out.print(root.val + " ");
            preOrder(root.right);
        }

        // 后序遍历
        void postOrder(TreeNode root) {
            if(root == null){
                return;
            }
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.val + " ");
        }

        public int nodeSize;

        /**
         * 获取树中节点的个数：遍历思路
         */
        void size(TreeNode root) {
            if(root == null){
                return;
            }
            nodeSize++;
            size(root.left);
            size(root.right);
        }

        /**
         * 获取节点的个数：子问题的思路
         *
         * @param root
         * @return
         */
        int size2(TreeNode root) {
            if(root == null){
                return 0;
            }
            return 1 + size2(root.left) + size2(root.right);
        }


        /*
         获取叶子节点的个数：遍历思路
         */
        public static int leafSize = 0;

        void getLeafNodeCount1(TreeNode root) {
            if(root == null){
                return;
            }
            if(root.left == null && root.right == null){
                leafSize++;
                return;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }

        /*
         获取叶子节点的个数：子问题
         */
        int getLeafNodeCount2(TreeNode root) {
            if(root == null){
                return 0;
            }
            return ((root.left == null && root.right == null) ? 1 : 0) + getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }

        /*
        获取第K层节点的个数
         */
        int getKLevelNodeCount(TreeNode root, int k) {
            if(root == null){
                return 0;
            }
            return (k == 1 ? 1 : 0) + getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
        }

        /*
         获取二叉树的高度
         时间复杂度：O(N)
         */
        int getHeight(TreeNode root) {
            if(root == null){
                return 0;
            }
            return 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }


        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, char val) {
            if(root == null){
                return null;
            }else if(root.val == val){
                return root;
            }
            TreeNode leftRet = find(root.left, val);
            TreeNode rightRet = find(root.right, val);
            if(leftRet != null){
                return leftRet;
            }else return rightRet;
        }

        //层序遍历
        void levelOrder(TreeNode root) {
            if(root == null){
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tmp = queue.poll();
                if(tmp.left != null){
                    queue.offer(tmp.left);
                }
                if(tmp.right != null){
                    queue.offer(tmp.right);
                }
                System.out.print(tmp.val + " ");
            }
        }


        // 判断一棵树是不是完全二叉树
        boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode tmp = queue.poll();
                if (tmp.left != null) {
                    queue.offer(tmp.left);
                }
                if (tmp.right != null) {
                    queue.offer(tmp.right);
                }
                if(tmp.left == null && tmp.right == null){
                    continue;
                }
                if(tmp.left == null && !queue.isEmpty()){
                        return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        System.out.println(tree.find(tree.root,'2'));
        System.out.println(tree.getKLevelNodeCount(tree.root, 1));
        System.out.println(tree.getLeafNodeCount2(tree.root));
        tree.getLeafNodeCount1(tree.root);
        System.out.println(BinaryTree.leafSize);
        tree.size(tree.root);
        System.out.println(tree.nodeSize);
        System.out.println(tree.size2(tree.root));
        tree.preOrder(tree.root);
        System.out.println();
        tree.inOrder(tree.root);
        System.out.println();
        tree.postOrder(tree.root);
        System.out.println();
        tree.levelOrder(tree.root);
        System.out.println();
        System.out.println(tree.isCompleteTree(tree.root));
    }
}
